/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：TreapTree.h
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-18
Function List ：
Description   ：Treap Tree
******************************************************/

#ifndef TREAPTREE_H_
#define TREAPTREE_H_

// Type Definition
struct TreapNode;
typedef int ElementType;
typedef struct TreapNode *Position;
typedef struct TreapNode *TreapTree;

// Function Lists
TreapTree Initialize(void);
TreapTree MakeEmpty(TreapTree T);
int IsEmpty(TreapTree T);
Position Find(ElementType X, TreapTree T);
Position FindMin(TreapTree T);
Position FindMax(TreapTree T);
TreapTree Insert(ElementType X, TreapTree T);
TreapTree Delete(ElementType X, TreapTree T);
Position Left(Position P);
Position Right(Position P);
ElementType Retrieve(Position P);
void PreorderTraversal(TreapTree T);
void InorderTraversal(TreapTree T);
void PostorderTraversal(TreapTree T);
void LevelorderTraversal(TreapTree T);

#endif  /* TREAPTREE_H_ */

// EOF

